An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (e.g., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment (particularly routers and switches), computer systems, cache tags, and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data in the comparand register. When the content stored in the CAM memory location does not match the data in the comparand register, the local match detection circuit returns a no match indication. When the content stored in the CAM memory location matches the data in the comparand register, the local match detection circuit returns a match indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address location in which the desired data is stored or one of such addresses if more than one address contained matching data. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
As with other semiconductor memory devices, CAMs can be susceptible to “soft errors,” where the data in the CAM is changing (or has changed) as a result of an unknown, or unpredictable event, such as a glitch. If the soft error is not detected, the data stored within the CAM will be incorrect and the application which relies upon the CAM will produce inaccurate results. In order to detect (and/or correct) soft errors, many memory systems incorporate parity bits. A parity bit is an additional bit appended to a memory word. The use of a single parity bit appended to each data word permits the memory system to detect single bit errors. The content of the parity bit is determined by a mathematical operation upon the data portion of the word. In many systems using a single parity bit per word, the value of the parity bit may be the exclusive OR (XOR) of each data bit in the word. A memory system can detect a single-bit soft error in a memory word by calculating the parity and storing the parity during the write of a data word and recalculating the parity based on the data read during a read operation and comparing the calculated parity with the read parity. If the calculated parity matches the read parity, the memory system can conclude that the data word was read without any single bit errors.
In a CAM the use of parity bits is problematic because CAM entries store not only data, but also status bits. That is, each CAM entry has a number of bits which store the data contents of the CAM and an additional plurality of bits used to store status information regarding that CAM entry. For example, commonly available status bits include a valid bit (for indicating whether CAM entry contains valid data), a permanence bit (for indicating whether a CAM entry should be “locked” in the CAM), a read bit (for indicating whether a CAM entry matches a search expression), etc. Additionally, some CAM support user defined status bits. The existence of status bits in a CAM is problematic because the status bits associated with one or more CAM entries may be changed without a change in the data portion of the associated CAM entries. For example, a search operation performed upon the CAM may cause a read bit in one or more entries to be changed without changing the data stored in those entries. A change in one status bit of an entry is a single bit change which would ordinarily be detected as a parity error if that entry were to be read. Accordingly, there is a desire and need for a mechanism to permit the use of parity bits with a CAM memory system.